package com.leetcode;
//给你一个下标从 0 开始的字符串 num ，表示一个非负整数。

//
// 在一次操作中，您可以选择 num 的任意一位数字并将其删除。请注意，如果你删除 num 中的所有数字，则 num 变为 0。
//
// 返回最少需要多少次操作可以使 num 变成特殊数字。
//
// 如果整数 x 能被 25 整除，则该整数 x 被认为是特殊数字。
//
//
//
//
//
// 示例 1：
//
//
//输入：num = "2245047"
//输出：2
//解释：删除数字 num[5] 和 num[6] ，得到数字 "22450" ，可以被 25 整除。
//可以证明要使数字变成特殊数字，最少需要删除 2 位数字。
//
// 示例 2：
//
//
//输入：num = "2908305"
//输出：3
//解释：删除 num[3]、num[4] 和 num[6] ，得到数字 "2900" ，可以被 25 整除。
//可以证明要使数字变成特殊数字，最少需要删除 3 位数字。
//
// 示例 3：
//
//
//输入：num = "10"
//输出：1
//解释：删除 num[0] ，得到数字 "0" ，可以被 25 整除。
//可以证明要使数字变成特殊数字，最少需要删除 1 位数字。
//
//
//
//
// 提示
//
//
// 1 <= num.length <= 100
// num 仅由数字 '0' 到 '9' 组成
// num 不含任何前导零
//
//
// Related Topics 贪心 数学 字符串 枚举 👍 60 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
public class No2844 {

    // 1、结尾只有 00 25 50 75 这四种可能
    // 2、数字 0
    public int minimumOperations(String num) {
        char[] chars = num.toCharArray();
        int min25 = minTime(chars, "25");
        int min50 = minTime(chars, "50");
        int min00 = minTime(chars, "00");
        int min75 = minTime(chars, "75");
        return Math.min(min25, Math.min(min00, Math.min(min50, min75)));
    }

    public int minTime(char[] chars, String lastNum) {
        int index = lastNum.length() - 1;
        boolean hasZero = false;
        int result = 0;
        for (int i = chars.length - 1; i >= 0; i--) {
            if (chars[i] == lastNum.charAt(index)) {
                index--;
            } else {
                result++;
            }
            if (chars[i] == '0') {
                hasZero = true;
            }
            if (index < 0) {
                break;
            }
        }
        if (index >= 0) {
            return hasZero ? chars.length - 1 : chars.length;
        }
        return result;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
